/**
 * @author LKQ
 * @date 2022/1/7 20:05
 * @description 动态规划 -最低有效位，正整数x，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数[x/2]
 */
public class FormalSolution2 {
    public static void main(String[] args) {

    }
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // i & 1 代表 i / 2 的余数即 i % 2;
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}
